package problem44;

//44.通配符匹配
//https://leetcode.cn/problems/wildcard-matching/

class Solution {
    public boolean isMatch(String s, String p) {
        s = " " + s;
        p = " " + p;
        int n = s.length(), m = p.length();
        boolean[][] dp = new boolean[n][m];
        dp[0][0] = true;
        for(int j = 1; j<m; j++) {
            if(p.charAt(j) == '*') dp[0][j] = true;
            else break;
        }
        for(int i = 1; i<n; i++) {
            for(int j = 1; j<m; j++) {
                if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {
                    dp[i][j] = dp[i-1][j-1];
                }else if(p.charAt(j) == '*') {
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                }
            }
        }
        return dp[n-1][m-1];
    }
}

/*
dp[i][j]:s的前i个字符能否匹配  p的前j个字符

p[j]=='*'
dp[i][j]  = dp[i][j-1] + dp[i-1][j-1] + dp[i-2][j-1] + dp[i-3][j-1] + .....
dp[i-1][j]=               dp[i-1][j-1] + dp[i-1][j-1] + dp[i-3][j-1] + ....
dp[i][j] = dp[i][j-1] + dp[i-1][j];

*/